# 回文链表： https://leetcode-cn.com/problems/palindrome-linked-list/submissions/

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 我的写法
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        """
            这题可以使用快慢指针， 定位到对应位置。然后比较对应位置是否相等
            定义low， fast 指针。 fast指针的定位，
            快慢指针， low一次移动一步， fast 一次移动两步。
            1 2 2 1, 1 2 3 2 1 就两种情况， fast分别道 最后节点， low到中间位置，为别为 第一个2， 3。
        """
        low = fast = head

        # 1. 找到中间位置 low位置
        while fast.next and fast.next.next:
            fast = fast.next.next
            low = low.next
        
        # 2. 将中间节点后的部分反转
        pre = None
        cur = low.next
        while cur:
            p = cur
            cur = cur.next
            p.next = pre
            pre = p
        
        # 开始比较： fast 指向后面反转部分的链表头
        t = head
        while pre:
            if pre.val != t.val:
                return False
            pre = pre.next
            t = t.next
            
        return True